package com.atguigu.mapreduce.Algorithm;

import java.util.Arrays;

/**
 * @author laberinto
 * @version 1.0
 * @date 2024/10/22 16:36
 * @package com.atguigu.mapreduce.Algorithm
 * @message \\计数排序
 * (⌓‿⌓)
 */
public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0){ return;}

        // 找到数组中的最大值
        int max = Arrays.stream(arr).max().getAsInt();
        // 创建计数数组，大小为最大值 + 1
        int[] count = new int[max + 1];

        // 统计每个元素的出现次数
        for (int num : arr) {
            count[num]++;
        }

        // 将结果写入原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始数组: " + Arrays.toString(arr));

        countingSort(arr);

        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}